The problem solved by the algorithm of the present invention is directed to the scheduling of a first plurality of jobs, each comprising multiple job steps, for processing on a second plurality of machines. Jobs and machines as used herein refer in the most general sense to any types of tasks which are performed on service facilities, e.g. the performance of a sequence of data processing steps on a respective sequence of data processing devices. More specifically, in the context of manufacturing, each job may comprise the plurality of processing steps required to fabricate a particular component, e.g. in silicon wafer processing, where each step is performed on a different processing machine, e.g. ion implanter, diffusion furnace, chemical vapor deposition chamber, etc.
The job scheduling problem has been shown in the art to be NP-complete, so that any exhaustive search through the solution space grows exponentially with the size of the problem. The solution is typically subject to the constraint that each job be scheduled for completion at or before some prescribed due time or as short a time after the due time as possible. All known practical solution methods fall into two categories, one category employing pure search techniques, e.g. branch-and-bound, and the other category using heuristic rules. The techniques in both categories are adapted for practice on a digital computer. In spite of the effort to minimize the amount of computation, the known search techniques nevertheless suffer from excessive demands on computer time. The largest problems reported in the art and solved by these methods remain less than ten jobs scheduled on less than ten machines.
With respect to the approaches employing heuristic rules, most such approaches currently known in the art are of the time-progression type. That is, the solution schedule is generated step-by-step. At each step in the solution process, a queue of jobs waits to be processed at each machine. The choice of which job to process next at each machine is based on heuristic rules, e.g. choose the job with the closest due time. While such heuristic approaches require less computing time as compared to the search techniques, they fail to provide good schedules. One reason for the failure of such approaches is their failure to anticipate future schedule bottlenecks. Heuristic rule approaches which look ahead in time in order to anticipate possible future schedule constraints have been proposed, e.g. in "Heuristics in Job Shop Scheduling" by Gere, Management Science, Vol. 13, 1966, pp. 167-190. The instant inventor is, however, not aware of any such methods generally adopted in the art.